package B刷题.贪心;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * @author wei.zhao
 * @description: 502.IPO
 * @date 2022年11月18日 15:04
 */
public class Code01_FindMaximizedCapital {

    /**
     * 时间复杂度太大了：每次都要从全部项目中资本够的、利润最大的、没做过的项目。
     */
    public int findMaximizedCapital1(int k, int w, int[] profits, int[] capital) {
        int result = w;
        // 已经做过的项目
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            // 选择能做的，利润最大项目
            int maxIndex = -1;
            for (int i1 = 0; i1 < capital.length; i1++) {
                if (capital[i1] <= result && !set.contains(i1) && (maxIndex == -1 || profits[i1] >= profits[maxIndex])) {
                    maxIndex = i1;
                }
            }
            // 没有能做的项目
            if (maxIndex == -1) {
                break;
            }
            // 资本金增加
            set.add(maxIndex);
            result += profits[maxIndex];
        }
        return result;
    }

    public int findMaximizedCapital2(int k, int w, int[] profits, int[] capital) {
        // 能做的项目利润大根堆
        PriorityQueue<Project> pQueue = new PriorityQueue<>((a, b) -> b.profit - a.profit);
        // 资本小根堆
        PriorityQueue<Project> cQueue = new PriorityQueue<>(Comparator.comparingInt(e -> e.capital));
        for (int i = 0; i < profits.length; i++) {
            cQueue.add(new Project(profits[i], capital[i]));
        }
        // 收集能做的项目
        while (!cQueue.isEmpty() && cQueue.peek().capital <= w) {
            pQueue.add(cQueue.poll());
        }
        int count = 0;
        while (count < k && !pQueue.isEmpty()) {
            Project poll = pQueue.poll();
            w += poll.profit;
            count++;
            // 更新能做的项目
            while (!cQueue.isEmpty() && cQueue.peek().capital <= w) {
                pQueue.add(cQueue.poll());
            }
        }
        return w;
    }


    public static class Project {
        public int profit;
        public int capital;

        public Project(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }

}
